Algorithm CH7 Quick sort
Algorithm CH7 Quicksort
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062029.png)
description
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062111.png)
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062132.png)
Partition
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062159.png)
Loop invarient
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062255.png)
Ex.
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062323.png)
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062343.png)
correctness
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062437.png)
performance
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062616.png)
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062638.png)
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423062744.png)
- Intuition for the average case
- 看最好跟最壞的分割情況,只差一個常數而已
- 而且會被
-notation蓋掉
- 而且會被
random version
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423063121.png)
![](https://raw.githubusercontent.com/z-hwa/webHomeImage/main/image/20240423063204.png)
analyse
worst case:
Average case:
Algorithm CH7 Quick sort
https://z-hwa.github.io/webHome/[object Object]/2024/04/30/Algorithm/Algorithm-CH7-Quick-sort/